题解 AT2364 【Colorful Balls】

发表于 | 更新于

题意$:N$ 个球排成一排，第个$i$球的颜色为$c_i$，重量为 $w_i$。我们定义「一次操作」为：选择两个颜色相同，且重量之和不超过$X$的球，交换它们的位置；或选择两个颜色不同，且重量之和不超过$Y$的球，交换它们的位置。问进行任意次操作后，可以得到多少种不同的颜色序列。输出答案对 $10^9+7$ 取模的结果。

显然如果有三个球$a,b,c$,如果$a$与$b$能交换,$b$与$c$能交换，那$a$与$c$一定能通过$b$的“媒介”交换（$a$先于$b$交换，$b$与$c$交换，$a$与$b$交换）。

于是我们可以把$a,b,c$缩在同一个连通块里。

由于不同颜色与相同颜色交换条件是不一样的，我们先考虑相同颜色。

显然只需要用最小值做“媒介”即可。

然后我们考虑跨颜色交换。我们发现只需要用全局最小值做“媒介”，也就是说对于某个点，先通过该颜色最小值换到全局最小值，再通过全局最小值换到其他点。如果与全局最小值颜色相同，那我们就只能用次小值做媒介。

这样我们只需要记录某种颜色的最小值、全局最小值、全局次小值即可。

然后我们不难发现含有不同颜色的连通块只有一个，那就是全局最小值所在的连通块。

而只有一种颜色的连通块对答案没有影响。

于是我们只考虑最小值所在的连通块。首先我们找到全局最小值、全局次小值与每种颜色的最小值。如果他们都不能交换，那显然是凉了（答案为11）。我们对每种颜色数出能与该种颜色最小值交换的点数，然后用每种连通块的最小值与全局最小值（全局次小值）比较，求出这个联通块。我们发现就是求这个联通块排列方案数，其实就是可重集合排列。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include <bits/stdc++.h>
#define inf 0x3f3f3f3f
#define int long long
#define mod 1000000007
#define N 200007
using namespace std;
inline int read(){
    int x=0,w=0;char ch=getchar();
    while (!isdigit(ch))w|=ch=='-',ch=getchar();
    while (isdigit(ch))x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
    return w?-x:x;
}
int ksm(int x,int k){
    int res=1;
    while(k){
        if(k&1)res=res*x%mod;
        x=x*x%mod;
        k>>=1;
    }
    return res;
}
int mn[N],c[N],w[N],cnt[N],jc[N],inv[N],n,A,B,ans;
signed main(){
//    freopen("keep.in", "r", stdin); freopen("keep.out", "w", stdout); 
    n=read(),A=read(),B=read();
    memset(mn,0x3f,sizeof(mn));
    jc[0]=1;
    for(int i=1;i<=n;i++)jc[i]=jc[i-1]*i%mod;
    inv[n]=ksm(jc[n],mod-2);
    for(int i=n-1;i>=0;i--)inv[i]=inv[i+1]*(i+1)%mod;
    for (int i=1;i<=n;++i){
        c[i]=read(),w[i]=read();
        mn[c[i]]=min(mn[c[i]],w[i]);//颜色集合最小值 
        ++cnt[c[i]];//集合元素个数 
    }
    int Mn=1,mnn=inf;
    for (int i=1;i<=n;++i)
        if (mn[i]<mn[Mn])
            Mn=i;//找出全局最小值的颜色 
    for (int i=1;i<=n;++i)
        if (i!=Mn)
            mnn=min(mn[i],mnn);//找出除全局最小值的集合以外的所有数的最小值 
    for (int i=1;i<=n;++i){
        if (w[i]!=mn[c[i]]&&w[i]+mn[c[i]]<=A)continue;//如果这个值不是所在集合的最小值但它与所在集合的最小值的和小于A，那么它是有意义的 
        if (c[i]!=Mn&&w[i]+mn[Mn]<=B)continue;//如果这个值不在全局最小值所在的集合中 ，但它与全局最小值的和小于B，那么它是有意义的
        if (c[i]==Mn&&w[i]+mnn<=B)continue;//如果它在全局最小值所在的集合中，且它与除全局最小值的集合以外的所有数的最小值的和小于B，那么它是有意义的 
        --cnt[c[i]];//如果它不符合以上条件，那么它的存在是没有意义的
    }
    int num=cnt[Mn];
    for (int i=1;i<=n;++i)
        if (i!=Mn&&mn[Mn]+mn[i]<=B)//如果这种颜色存在且它不是全局最小值所在的集合 
            num+=cnt[i];
    ans=1;
    for (int i=1;i<=n;++i)
        if(mn[i]!=inf&&(i==Mn||mn[i]+mn[Mn]<=B))
            ans=ans*inv[cnt[i]]%mod;
    for (int i=1;i<=num;++i)
        ans=ans*i%mod;//这里是求有重复元素的排列种数 
    printf("%lld",ans);
}